// 杨辉三角
/*给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
*/
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> arr;
        for (int i = 1; i <= numRows; i++) {
            vector<int> _arr(i, 1);
            arr.push_back(_arr);
        }
        for (int i = 2; i < numRows; i++) {
            for (int j = 1; j < arr[i].size() - 1; j++) {
                arr[i][j] = arr[i - 1][j] + arr[i - 1][j - 1];
            }
        }
        return arr;
    }
};

//只出现一次的数字 III
/*给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
2 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
除两个只出现一次的整数外，nums 中的其他数字都出现两次
 */

 class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int x = 0;
        for (auto& val : nums) {
            x ^= val;
        }
        if (x != INT_MIN) {
            x = x & (-x);
        }
        int num1 = 0;
        int num2 = 0;
        for (auto& val : nums) {
            if (val & x) {
                num1 ^= val;
            } else {
                num2 ^= val;
            }
        }
        vector<int> arr;
        arr.push_back(num1);
        arr.push_back(num2);
        return arr;
    }
};


//反转链表
/*给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000
*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr)
            return head;
        ListNode* n1 = nullptr;
        ListNode* n2 = head;
        ListNode* n3 = head->next;
        while (n2) {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if (n3)
                n3 = n3->next;
        }
        return n1;
    }
};

// 只出现一次的数字 II
/*给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
1 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
*/
class Solution {
public:
    int singleNumber(vector<int>& nums) {

        int x = 0;
        for (int i = 0; i < 32; i++) {
            int sum = 0;
            for (auto& val : nums) {
                sum = (sum + ((val >> i) & 1)) % 3;
            }
            if (sum) {
                x |= (1 << i);
            }
        }
        return x;
    }
};

